package main

import "fmt"

/*
0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:
输入: [0,1,3]
输出: 2

示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
*/

func missingNumber(nums []int) int {
	//从小到大排序 二分法
	var left, right = 0, len(nums) - 1
	for left <= right {
		m := (left + right) / 2
		if nums[m] == m { //下标等于值 说明缺失的数字还在后面 l变大
			left = m + 1
		} else { //下标不等于值 说明缺失的数字在前面 r变小
			right = m - 1
		}
	}
	return left
}

func main() {
	n := []int{0, 1, 2, 3, 4, 5, 6, 7, 9}
	fmt.Println(missingNumber(n))
}
